package gold.gold02;

import java.util.Arrays;

/**
 * 二进制
 */
public class S0504下一个数 {
    /**
     * 15, 直接穷举, 因为是最近的一个, 所以也能通过。大家时间差不多。
     */
    public int[] findClosedNumbers2(int num) {
        if(num == Integer.MAX_VALUE) return new int[]{-1, -1};
        int[] result = new int[]{-1, -1};
        int originCount = cacuNum(num);

        for(int i = num + 1; i <= Integer.MAX_VALUE; i++){
            if(cacuNum(i) == originCount){
                result[0] = i;
                break;
            }
        }

        for(int i = num - 1; i >= (int)Math.pow(2, originCount - 1); i--){
            if(cacuNum(i) == originCount) {
                result[1] = i;
                break;
            }
        }
        return result;

    }
    public int cacuNum(int num){
        char[] temp1 = Integer.toBinaryString(num).toCharArray();
        int count = 0;
        for(char c : temp1){
            if(c == '1') count ++;
        }
        return count;
    }

    /**
     * 不行, 不太清楚这个下一个数, 和当前数应该是一个怎样的数学关系, 猜测是其中最低位的一组0/1互换。
     * 不行, 互换一些情况下不合适。
     */
    public int[] findClosedNumbers(int num) {
        if(num == Integer.MAX_VALUE) return new int[]{-1, -1};
        int[] result = new int[]{-1, -1};
        int[] numBin = new int[32];
        char[] temp1 = Integer.toBinaryString(num).toCharArray();
        for(int i = 0; i < temp1.length; i++){
            if(temp1[i] == '1') numBin[32 - temp1.length + i] = 1;
        }
        System.out.println(Arrays.toString(numBin));
        int[] lowNumBin = Arrays.copyOfRange(numBin, 0, numBin.length);
        int[] highNumBin = Arrays.copyOfRange(numBin, 0, numBin.length);
        // 比num小的那个数
        boolean flag = false;
        here:
        for(int i = 0; i < 32; i++){
            if(lowNumBin[32 - 1 - i] == 1){
                for(int j = i - 1; j >= 0; j--){
                    if(lowNumBin[32 - 1 - j] == 0){
                        lowNumBin[32 - 1 - j] = 1;
                        lowNumBin[32 - 1 - i] = 0;
                        flag = true;
                        break here;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(lowNumBin));
        if(flag){
            result[1] = 0;
            for(int i = 0; i < 32; i++){
                if(lowNumBin[32 - 1 - i] == 1)
                    result[1] += (int)Math.pow(2, i);
            }
        }
        // 比num大的那个数
        flag = false;
        here:
        for(int i = 0; i < 32; i++){
            if(highNumBin[32 - 1 - i] == 0){
                for(int j = i - 1; j >= 0; j--){
                    if(highNumBin[32 - 1 - j] == 1){
                        highNumBin[32 - 1 - j] = 0;
                        highNumBin[32 - 1 - i] = 1;
                        flag = true;
                        break here;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(highNumBin));
        if(flag){
            result[0] = 0;
            for(int i = 0; i < 32; i++){
                if(highNumBin[32 - 1 - i] == 1)
                    result[0] += (int)Math.pow(2, i);
            }
        }
        return result;
    }
    /**
     * 正经位运算, 对的, 主要还是把低位的部分也要位移。
     *
     * 最接近的较小值:二进制表示中从右向左找前面有0的第一个1,"10"中的1,0换位,剩下右边的二进制位前后翻转
     * 解释:从低位向高位找第一个可以被低位0替换的1使数变小,同时低位在保持0,1个数不变时要尽可能大,
     * 分析发现在满足前面查找条件右边的0,1分布:空,"0000"(全是0),“0011”(全1开始全0结束)和“11111”(全是1),
     * 只需要把他们前后翻转就能把所有1移动到高位实现剩余右边值最大
     * 最接近的较大值:二进制表示中从右向左找前面有1的第一个0,"01"中的1,0换位,剩下右边的二进制位前后翻转
     * 解释:从低位向高位找第一个可以被低位1替换的0使数变大,同时低位在保持0,1个数不变时要尽可能小,
     * 分析发现在满足前面查找条件右边的0,1分布:空,"0000"(全是0),“1100”(全0开始全1结束)和“11111”(全是1),
     * 只需要把他们前后翻转就能把所有0移动到高位实现剩余边右值最小
     */
    public int[] findClosedNumbers3(int num) {
        int [] re={-1,-1};
        int flag1=0;
        int flag2=0;
        int temp=num;
        int cur;
        for(int i=0;i<31&&(flag1<2 || flag2<2);i++){
            cur=temp&1;
            temp=temp>>1;
            if(flag1==0&&cur==0){
                flag1=1;
            }else if(flag1==1 && cur==1){
                flag1=2;
                re[1]=(int)(num-Math.pow(2,i)+Math.pow(2,i-1));
                int temp1=re[1]&(((int)Math.pow(2,i-1))-1);
                re[1]=re[1]>>(i-1);
                for(int j=0;j<i-1;j++){
                    re[1]=((re[1]<<1)|(temp1&1));
                    temp1=temp1>>1;
                }
            }
            if(flag2==0&&cur==1){
                flag2=1;
            }else if(flag2==1 && cur==0){
                flag2=2;
                re[0]=(int)(num-Math.pow(2,i-1)+Math.pow(2,i));
                int temp1=re[0]&(((int)Math.pow(2,i-1))-1);
                re[0]=re[0]>>(i-1);
                for(int j=0;j<i-1;j++){
                    re[0]=((re[0]<<1)|(temp1&1));
                    temp1=temp1>>1;
                }
            }
        }
        return re;
    }

}
